package com.dlut.java;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Random;
import java.util.Scanner;

public class T2_GroupQuestions {
    public static void main(String[] args) {
/*
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[n];
        int[] b = new int[n];
        int[] c = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();
        }
        for (int i = 0; i < n; i++) {
            b[i] = in.nextInt();
        }
        for (int i = 0; i < n; i++) {
            c[i] = in.nextInt();
        }
        int ans = fun2(a, b, c, n);
        System.out.println(ans);
*/
        for (int i = 0; i < 10000; i++) {
            boolean b = test();
            if (! b){
                System.out.println("出错了");
            }
        }
        System.out.println("成功了");

    }

    /**
     * 随机数测试
     */
    public static Random random = new Random();
    public static boolean test(){
        int n = random.nextInt(200) + 1;
        int[] a = new int[n];
        int[] b = new int[n];
        int[] c = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = random.nextInt(10000);
            b[i] = random.nextInt(10000);
            c[i] = random.nextInt(10000);
        }
        int ans = fun(a, b, c, n);
        int ans2 = fun2(a, b, c, n);
//        System.out.println(ans == ans2);
        return ans == ans2;
    }

    /**
     * 双指针加二分查找
     * @param a
     * @param b
     * @param c
     * @param n
     * @return
     */
    public static int fun2(int[] a, int[] b, int[] c, int n){
        Arrays.sort(a);
        Arrays.sort(b);
        Arrays.sort(c);
        int count = 0;
        int left = 0, right = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            while (right < n && b[right] <= a[i] * 2){
                right ++;
            }
            while (left < n && b[left] <= a[i]){
                left ++;
            }
            for (int j = left; j < right; j++) {
                if (map.containsKey(b[j])){
                    count += map.get(b[j]);
                }else{
                    int l = search(c,b[j]);
                    int r = search(c,b[j] * 2);
                    count += r - l;
                    map.put(b[j], r - l);
                }
            }
        }
        return count;
    }
    // 二分查找
    private static int search(int[] c, int i) {
        int n = c.length;
        int l = 0, r = n - 1;
        int mid = 0;
        while (l <= r){
            mid = l + (r - l) / 2;
            if (c[mid] <= i){
                l = mid + 1;
            }else {
                r = mid - 1;
            }
        }
        return l;
    }

    /**
     * 暴力循环，进行对比测试
     * @param a
     * @param b
     * @param c
     * @param n
     * @return
     */
    public static int fun(int[] a, int[] b, int[] c, int n){
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    if (a[i] < b[j] && a[i] * 2 >= b[j]){
                        if (b[j] < c[k] && b[j] * 2 >= c[k]){
                            ans ++;
                        }
                    }
                }
            }
        }
        return ans;
    }
}
